# 第4节 再解炸弹人
a = [
    ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
    ['#', 'G', 'G', '.', 'G', 'G', 'G', '#', '.', '#'],
    ['#', '#', '#', 'G', '#', '.', 'G', 'G', 'G', '#'],
    ['#', '#', '.', '.', '#', 'G', '#', '#', '#', '#'],
    ['#', '.', '#', 'G', '#', 'G', 'G', 'G', '.', '#'],
    ['#', '.', '#', 'G', '.', '.', '#', '#', 'G', '#'],
    ['#', '#', '.', 'G', 'G', 'G', 'G', '.', 'G', '#'],
    ['#', 'G', '.', '#', '.', '#', '.', '.', '#', '#'],
    ['#', '#', '#', '.', '#', '#', 'G', 'G', '.', '#'],
    ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#'],
    ['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
]


class Note:

    def __init__(self):
        self.x = 0
        self.y = 0


def get_num(i, j):
    sum = 0
    # 向上统计消灭的敌人
    x = i
    y = j
    while a[x][y] != '#':
        if a[x][y] == 'G':
            sum += 1
        x -= 1

    # 向下统计消灭的敌人
    x = i
    y = j
    while a[x][y] != '#':
        if a[x][y] == 'G':
            sum += 1
        x += 1
    # 向左
    x = i
    y = j
    while a[x][y] != '#':
        if a[x][y] == 'G':
            sum += 1
        y -= 1

    # 向右
    x = i
    y = j
    while a[x][y] != '#':
        if a[x][y] == 'G':
            sum += 1
        y += 1
    return sum


if __name__ == '__main__':
    print('开始执行')
    max = 0
    # 下一步 右 下 坐 上
    next_array = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    que = [Note() for i in range(1, 401)]  # 假设地图人小不超过20*20，因此队列扩展不会超过400个
    # 标记哪些点已经记录到队列中
    book = [[0 for i in range(21)] for j in range(21)]
    # 行数
    m = len(a)
    n = len(a[0])
    head = 1
    tail = 1
    startx = 2
    starty = 3
    que[tail].x = startx
    que[tail].y = starty
    tail += 1
    book[startx][starty] = 1
    max = get_num(startx, starty)
    mx, my = startx, starty
    print(max)
    while head < tail:
        # 枚举四种走法
        for k, v in enumerate(range(0, 4)):
            # print(k)
            # print(k)
            # 计算下一个坐标
            tx = que[head].x + next_array[k][0]
            ty = que[head].y + next_array[k][1]
            # 判断是否越界
            if tx < 1 or tx > n or ty < 1 or ty > m:
                continue
            if a[tx][ty] == '.' and book[tx][ty] == 0:
                book[tx][ty] = 1
                que[tail].x = tx
                que[tail].y = ty
                tail += 1
                sum = get_num(tx, ty)
                print("将炸弹放在(%d,%d)处可以消灭%d个敌人" % (tx, ty, sum))
                if sum > max:
                    max = sum
                    mx = tx
                    my = ty
        head += 1  # 一个点结束后进行下一个点
    print("最终结果：将炸弹放在(%d,%d)处可以消灭%d个敌人" % (mx, my, max))
